1. Field of the Invention
The present invention generally relates to data processing for the digital transmission, storage, retrieval and display of arbitrary images and, more particularly to the rapid decoding of images from digital data for presentation in potentially rapid sequence.
2. Description of the Prior Art
Pictorial and graphics images contain extremely large amounts of data and, if digitized to allow transmission or processing by digital data processors and exploitation of various benefits of digital transmission, such as increased noise immunity and error recovery, often require many millions of bytes to represent respective pixels of the image or graphics with good fidelity. The sheer quantity of data in images therefore presents a severe processing burden. However, pictorial data is often susceptible to substantial data compression without significant loss of image fidelity. That is, image data compression often allows representation of images with less data in order to save storage costs or transmission time and costs with little or no perceptible effect on image fidelity.
The most effective compression is achieved by approximating the original image, rather than reproducing it exactly. The JPEG standard, discussed in detail in “JPEG Still Image Data Compression Standard” by Pennebaker and Mitchell, published by Van Nostrand Reinhold, 1993, which is hereby fully incorporated by reference, allows the interchange of images between diverse applications and provides the capability of producing digital continuous-tone color images in multi-media applications.
JPEG is primarily concerned with images that have two spatial dimensions, contain gray scale or color information, and possess no temporal dependence, as distinguished from the MPEG (Moving Picture Experts Group) standard. JPEG compression can reduce the storage requirements by more than an order of magnitude and improve system response time in the process. A primary goal of the JPEG standard is to provide the maximum image fidelity for a given volume of data and/or available transmission bandwidth or processing time and any arbitrary degree of data compression can be accommodated although, depending on image content, data compression may be limited by loss of the image detail or features of interest. However, it is often the case that data compression by a factor of twenty or more (and reduction of transmission or processing time and storage capacity by a comparable factor) will not produce artifacts which are noticeable to the average viewer.
The JPEG standard should be viewed as a family of compression techniques which have different properties and imply different advantages in regard to hardware requirements, processing time and the like. Since maximum preservation of image fidelity relative to image data file size and the flexibility to customize compression techniques to exploit characteristics of image content are principal goals of the JPEG standard, encoding and decoding may be computationally intensive and require significant amounts of time for a single image, particularly since JPEG coding and decoding is usually carried out in software (since it is generally efficient to download the particular portion of JPEG corresponding to the image content with the image rather than to determine the particular JPEG family member with the properties best corresponding to image and file content from resident software or hardware) and the higher speeds of special purpose chips are not generally available to most users. Therefore, the JPEG standard also allows various modes of operation such as are referred to as sequential or progressive in order to more quickly present a portion of the image or the full image at reduced resolution (increasing over time), respectively, so that the image may be more quickly identified and processing terminated and begun on another image if it is determined that a particular image is not of interest upon viewing of a partially decoded image. Iterating through a sequence of images is often referred to as browsing.
It can be appreciated that when a person may wish to look through a group of hard-copy images, such as photographs, each image may be viewed for only a fraction of a second in order to find and/or select an image of interest. It is desirable to be able to provide a similar capability in displaying images from digital data. Therefore, it has been the practice to use sequential or progressive operation of JPEG standard compression techniques to deliver an increasing fraction of the image at full detail or the full image at increasing resolution so that an image which is not desired can be rejected as soon as it is recognizable by the viewer. However, software implementations of JPEG processing may not allow the frequency of image presentation to be acceptably high consistent with providing images adequate for recognition.
The situation is somewhat different under the MPEG standard which must support image frame rates above the flicker fusion frequency of human visual perception. To do so, additional compression is provided by exploiting data which remains constant between frames, image motion sensing and prediction for interpolation to reduce decoding demands and the like. The subject matter of the data for which MPEG compression is used will also generally include long sequences of related images such as are presented in a motion picture which is marketed to subscribers. Therefore, the intended market economically supports the widespread availability of set-top boxes (STBs) including special purpose data processing chips capable of very fast decoding and presentation of images.
However, MPEG decoders and the MPEG standard itself are not well-adapted to decoding of sequences of independent images (even though independent “I-frame” images are periodically decoded, with intra-coded B-frames and P-frames between them, in accordance with the MPEG standard) and cannot be directly used for single images encoded under the JPEG standard while preserving the detail and fidelity desired in single images. In fact, since the anticipated applications for JPEG and MPEG were quite different when those standards were promulgated, incompatibilities between the coding techniques were tolerated such that transcoding from JPEG to MPEG data was not considered practical or even possible without unacceptable reduction of image quality even though MPEG to JPEG transcoding was supported.
For example, so-called “oddification” (described at page 272 of “MPEG Video Compression Standard”, published by Chapman & Hall, New York, N.Y., 1997, which is hereby fully incorporated by reference) provided in the MPEG standard unavoidably leads to a reduction in image fidelity in any transcoding from JPEG to MPEG. Therefore, while economically justifiable, the utility of special purpose moving picture decoder chips and STBs is quite limited relative to the amount of compressed digital image data and digitized and compressed libraries of images currently available and foreseeable.
Many libraries of images have been developed in which rapid browsing is desirable. In addition to increased use of digital electronic cameras by individuals and which present many advantages over film cameras (not the least of which encourages the generation of increased numbers of images, many of which may be later discarded and storage space reused), electronic files are being increasingly used to archive and provide rapid access to large quantities of documents, such as personal checks, negotiable certificates, legal records and the like.
Among such documents, a person may wish to browse images based on an arbitrarily located area such as check number or payee. The location of this information in the image may be inconsistent with progressive (since detail is not immediately available) or sequential (since the region of interest may not be near the top of the document) JPEG operation. Further, in such a case, the nature of the browsing done may require even less viewing time per image that can be conveniently allowed to determine that a particular image is not of interest.
In summary, while JPEG processing provides optimal single image quality for a given data volume, it is only widely available in software implementations that do not support desired image presentation frequencies for browsing or full image presentation or full resolution at presentation rates (or throughput in regard to, for example, decoding of a single image or several images which may each be very large) approaching those frequencies. Current applications do not economically support widespread availability of special purpose hardware to increase JPEG encoded image presentation speed notwithstanding the development of many libraries which would most desirably be accessed by browsing. Widely available MPEG hardware capable of suitably high image presentation frequency is not compatible with JPEG encoded data and, at the present state of the art, transcoding from JPEG to MPEG is considered to be impractical and to lead to unavoidable and generally unacceptable reduction in image fidelity, particularly if the transcoding process is lossy.
In this regard, transcoding of incompatible formats for lossless data compression is known. FIG. 5-17 on page 77 of the above-incorporated JPEG text illustrates transcoding between the Huffman and Arithmetic entropy coders for the JPEG standard. Converting the Group 3 facsimile standard into the better compressing Group 4 facsimile standard has been often done once the error recovering built into the Group 3 standard is not needed (e.g. inside computer systems). Karl M. Marks, (“A JBIG-ABIC compression engine for digital document processing,” IBM Journal of Research and Development, Vol 42, No. 6 pp. 753-758 (November 1998)) describes a chip that can encode or decode the bi-level image compression algorithms JBIG and ABIC. Thus conversion between them was made easy. The worst case for JBIG was not acceptable and so temporary storage of the documents converted into the ABIC version was preferred.